#pragma once
#include <algorithm>
#include <list>
#include <map>
#include <mutex>
#include <unordered_map>

#include "ArcNode.h"

namespace Cache
{

template<typename K, typename V>
class LfuPart
{
public:
    using NodeType = ArcNode<K, V>;
    using NodePtr = std::shared_ptr<NodeType>;
    using NodeMap = std::unordered_map<K, NodePtr>;
    using FreqMap = std::map<size_t, std::list<NodePtr>>;
private:
    size_t _mainCapacity;
    size_t _ghostCapacity;
    size_t _chargeFlag;
    size_t _minFreq;
    std::mutex _mutex;

    NodeMap _mainCaches;
    NodeMap _ghostCaches;
    FreqMap _freqMap;

    NodePtr _ghostHead;
    NodePtr _ghostTail;

public:
    explicit LfuPart(size_t capacity,size_t _chargeFlag)
        :_mainCapacity(capacity)
        ,_ghostCapacity(capacity)
        ,_chargeFlag(_chargeFlag)
        ,_minFreq(0)
    {
        initializeLists();
    }

    bool put(K key, V value)
    {
        if (_mainCapacity == 0)
        {
            return false;
        }

        std::unique_lock<std::mutex> lock(_mutex);
        auto it = _mainCaches.find(key);
        if (it != _mainCaches.end())
        {
            return updateExistingNode(it->second, value);
        }
        return addNewNode(key, value);
    }

    bool get(K key, V& value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        auto it = _mainCaches.find(key);
        if (it != _mainCaches.end())
        {
            value = it->second->getValue();
            updateNodeFrequency(it->second);
            return true;
        }
        return false;
    }

    bool contain(K key)
    {
        return _mainCaches.find(key) != _mainCaches.end();
    }

    bool checkGhost(K key)
    {
        auto it = _ghostCaches.find(key);
        if (it != _ghostCaches.end())
        {
            removeFromGhost(it->second);
            _ghostCaches.erase(it);
            return true;
        }
        return false;
    }

    void increaseCapacity() { ++_mainCapacity; }

    bool decreaseCapacity()
    {
        if (_mainCapacity == 0) return false;
        if (_mainCaches.size() == _mainCapacity)
        {
            evictLeastFrequent();
        }
        --_mainCapacity;
        return true;
    }

private:
    void initializeLists()
    {
        _ghostHead = std::make_shared<NodeType>();
        _ghostTail = std::make_shared<NodeType>();
        _ghostHead->_next = _ghostTail;
        _ghostTail->_prev = _ghostHead;
    }

    bool updateExistingNode(NodePtr node, V value)
    {
        node->setValue(value);
        updateNodeFrequency(node);
        return true;
    }

    bool addNewNode(K key, V value)
    {
        if (_mainCaches.size() >= _mainCapacity)
        {
            evictLeastFrequent();
        }

        NodePtr newNode = std::make_shared<NodeType>(key, value);
        _mainCaches[key] = newNode;

        //将新节点放到频率为一的列表
        if (_freqMap.find(1) == _freqMap.end())
        {
            _freqMap[1] = std::list<NodePtr>();
        }
        _freqMap[1].push_back(newNode);
        _minFreq = 1;
        return true;
    }

    void updateNodeFrequency(NodePtr node)
    {
        size_t oldFreq = node->getAccessCount();
        node->inAccessCount();
        size_t newFreq = node->getAccessCount();

        //从旧的频率表中删除
        auto& oldList = _freqMap[oldFreq];
        oldList.remove(node);
        if (oldList.empty())
        {
            _freqMap.erase(oldFreq);
            if (oldFreq == _minFreq)
            {
                _minFreq = newFreq;;
            }
        }
        //添加到新频率列表
        if (_freqMap.find(newFreq) == _freqMap.end())
        {
            _freqMap[newFreq] = std::list<NodePtr>();
        }
        _freqMap[newFreq].push_back(node);

    }

    void evictLeastFrequent()
    {
        if (_freqMap.empty())
        {
            return;
        }

        //获取最小频率的列表
        auto& minFreqList = _freqMap[_minFreq];
        if (minFreqList.empty())
        {
            return;
        }
        //移除最少使用的节点
        NodePtr leastNode = minFreqList.front();
        minFreqList.pop_front();

        //如果该频率列表变成了空，删除
        if (minFreqList.empty())
        {
            _freqMap.erase(_minFreq);

            //更新最小频率
            if (!_freqMap.empty())
            {
                _minFreq = _freqMap.begin()->first;
            }
        }

        //将节点移动到幽灵缓存
        if (_ghostCaches.size() >= _ghostCapacity)
        {
            removeOldestGhost();
        }
        addToGhost(leastNode);

        // 从主缓存中移除
        _mainCaches.erase(leastNode->getKey());

    }

    void removeOldestGhost()
    {
        NodePtr oldestGhost = _ghostHead->_next;
        if (oldestGhost != _ghostTail)
        {
            removeFromGhost(oldestGhost);
            _ghostCaches.erase(oldestGhost->getKey());
        }
    }

    void removeFromGhost(NodePtr node)
    {
        if (!node->_prev.expired() && node->_next)
        {
            auto prev = node->_prev.lock();
            prev->_next = node->_next;
            node->_next->_prev = node->_prev;
            node->_next = nullptr;
        }
    }
    void addToGhost(NodePtr node)
    {
        node->_next = _ghostTail;
        node->_prev = _ghostTail->_prev;
        if (!_ghostTail->_prev.expired()) {
            _ghostTail->_prev.lock()->_next = node;
        }
        _ghostTail->_prev = node;
        _ghostCaches[node->getKey()] = node;
    }

};

}

